package graph;

import java.util.HashSet;
import java.util.Vector;

/**
 * O(v+e),tested
 * 
 * @author yinzichen
 * 
 */
public class TarjanBCCBridge {
	Vector<HashSet<Integer>> bidirectedAdj;
	int[] used;
	int[] num;
	int[] low;
	int id;

	/**
	 * @param bidirectedGraph
	 *            edge(a,b) must have corresponding edge(b,a), if visit and
	 *            remove edge(a,b), then edge(b,a) should also be removed.
	 * @return
	 */
	public void bridge(Vector<HashSet<Integer>> bidirectedGraph) {
		int n = bidirectedGraph.size();
		bidirectedAdj = bidirectedGraph;
		used = new int[n];
		num = new int[n];
		low = new int[n];
		id = 0;
		for (int i = 0; i < n; ++i) {
			if (used[i] == 0) {
				dfs(i);
			}
		}
	}

	private void remove(int u, int v) {
		HashSet<Integer> adjU = bidirectedAdj.get(u);
		adjU.remove(v);
		HashSet<Integer> adjV = bidirectedAdj.get(v);
		adjV.remove(u);
	}

	private int dfs(int u) {
		num[u] = id;
		low[u] = id++;
		used[u] = 1;
		while (bidirectedAdj.get(u).size() > 0) {
			int v = bidirectedAdj.get(u).iterator().next();
			remove(u, v);
			if (used[v] == 0) {
				int f = dfs(v);
				if (f > num[u]) {
					// (u <-> v) is a bridge
					System.out.println(u + " " + v);
				}
				low[u] = Math.min(low[u], f);
			} else if (used[v] == 1) {
				low[u] = Math.min(low[u], num[v]);
			}
		}
		used[u] = 2;
		return low[u];
	}
}
